package ex.algorithms.sorting;

import ex.util.CommonUtil;

public class MedianSelect {
	public static int selectSmallest(int[] input, int index) {
		if(input == null || input.length < 2)
			return 0;
		
		return selectSmallest(input, 0, input.length-1, index);
		
	}
	
	private static int selectSmallest(int[] input, int start, int end, int index) {
		if(start == end)
			return input[start];
		
		int pivot = partition(input, start, end);
		int k = pivot - start + 1;
		if(k == index)
			return input[pivot];
		else if(index < k)
			return selectSmallest(input, start, pivot-1, index);
		else
			return selectSmallest(input, pivot+1, end, index-k);
	}
	
	private static int partition(int[] input, int start, int end) {
		int pivotValue = input[end];
		int i = start-1;
		for(int j=start; j<end; j++) {
			if(input[j] <= pivotValue) {
				i++;
				CommonUtil.swap(input, j, i);
			}
		}
		
		CommonUtil.swap(input, i+1, end);
		return i+1;
	}
}
